package gold.gold04;

import java.util.Arrays;

/**
 *
 */
public class S1011峰与谷 {
    /**
     * 别人的, 挺好。
     * https://leetcode-cn.com/problems/peaks-and-valleys-lcci/solution/onshi-jian-fu-za-du-by-jerry_nju/
     */
    public void wiggleSort3(int[] nums) {
        int n = nums.length;
        for(int i = 1;i < n; i++){
            //如果是奇数，且小于前面的，或者如果是偶数，且大于前面的，那就要交换
            if(((i & 1) == 1 && nums[i] < nums[i-1])||((i &1) == 0 && nums[i] > nums[i-1])){
                int temp = nums[i];
                nums[i] = nums[i-1];
                nums[i-1] = temp;
            }
        }
    }

    /**
     * 47, 先排个序, 然后大小逐个拿。logN复杂度。
     * 注意:
     */
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int start = 0, end = nums.length - 1;
        int[] res = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            if(i % 2 == 0) // 可以改成 if((i & 1) == 0), 这种使用位的方式更快。
                res[i] = nums[end--];
            else
                res[i] = nums[start++];
        }
        for(int i = 0; i < nums.length; i++){
            nums[i] = res[i];
        }
    }
    /**
     * 47, 排序后两两交错一下, 省点空间, 时间和上面的一样, 大部分时间还是在排序这里。
     */
    public void wiggleSort2(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 1; i = i + 2){
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
}
